Trójmiasto
Limit pamięci: 128 MB
W Bajtocji jest
miast, których położenie możemy przedstawić w postaci punktów na płaszczyźnie o całkowitych
współrzędnych. Odległość między dwoma miastami o współrzędnych
i
jest
określona w standardowy sposób:
.
Król Bajtocji, Bajtazar, chce wyznaczyć trzy miasta, które połączy i zamieni w Trójmiasto (wzorem pewnego egzotycznego królestwa, w którym w Trójmieście odbywają się finały
tamtejszej OI oraz rozmaitych międzynarodowych zawodów programistycznych).
Bajtazar postanowił wybrać takie trzy miasta, dla których suma odległości pomiędzy każdymi
dwoma z nich jest minimalna.
Wejście
Pierwszy wiersz standardowego wejścia zawiera jedną liczbę całkowitą
(
) oznaczającą liczbę miast w Bajtocji.
Miasta są ponumerowane od 1 do
.
W kolejnych
wierszach znajdują się po dwie liczby całkowite
i
(
)
oddzielone pojedynczym odstępem, oznaczające współrzędne
-tego wierzchołka miasta.
Możesz założyć, że w testach wartych łącznie
punktów zachodzi dodatkowy warunek
,
a w testach wartych łącznie
punktów zachodzi
.
Wyjście
Pierwszy wiersz standardowego wyjścia powinien zawierać jedną liczbę,
równą minimalnej sumie odległości pomiędzy miastami wybranego Trójmiasta,
zapisaną z dokładnością do dwóch miejsc po przecinku.
Przykład
Dla danych wejściowych:
5
0 0
0 3
0 8
4 0
5 4
poprawną odpowiedzią jest:
12.00
Wyjaśnienie do przykładu: Bajtazar wybierze miasta: 1, 2 i 4.
Autor zadania: Jacek Tomasiewicz.